1. Field of the Invention
The present invention relates to a variable length encoding/decoding apparatus using re-association of a symbol-codeword for a pre-defined code table.
2. Description of Related Art
Generally, data compression/decompression systems use quantization and orthogonal transform to reduce redundancy in the data especially for image data. A variable length coding (VLC) method which belongs to a lossless encoding method is often employed additionally to further compress data.
In block-based image data compression, a variable length coding method uses a zigzag scan to produce a "run" value and a "level" value from transform coefficients which are obtained by orthogonal transform. The variable length coding method uses a Huffman code table to change a symbol having a run value and a level value into a codeword. Here, the run value represents the number of successive zeros before a non-zero value and the level value is an absolute value of a non-zero coefficient succeeding the successive zeros. In the case where a symbol is represented as a pair of run and level values, if a run value or a level value is large, a frequency of occurrence of the symbol becomes statistically very low. Thus, the Huffman coding method which is generally used in the VLC method uses a codeword having a relatively short length for a symbol having a higher frequency of occurrence on the basis of probabilities of symbol occurrences. The Huffman code table shows that a relatively shorter codeword is allocated to a symbol having a higher frequency of occurrence, and a relatively longer codeword is allocated to a symbol having a lower frequency of occurrence. A pre-defined Huffman code table is generally used depending on the overhead and delay time. FIG. 1 shows a conventional variable length coding apparatus that uses the Huffman code table which is designed in the above-described manner.
A code table unit 15 of FIG. 1 stores the Huffman code table which is designed by the above-described method. A variable length encoder 11 finds a codeword corresponding to an input symbol from the Huffman code table stored in the code table unit 15 and outputs the corresponding codeword. Typically, the input symbol is used as an address at which the corresponding codeword is stored. Thus, if a variable length decoder (not shown) uses the same Huffman code table as that of the code table unit 15, the variable length decoder can retrieve the symbol from the transmitted codeword.
However, when a relationship between symbols and codewords as defined in the pre-defined Huffman code table does not reflect properly the actual probabilities of symbol occurrences as in the case where a symbol corresponding to a lengthy codeword has a higher frequency of occurrence, data compression efficiency through the VLC method can be significantly limited.
Prior art which attempts to solve the above problem is disclosed in U.S. Pat. No. 5,086,439 to Asai et al., entitled "Encoding/decoding system utilizing local properties" which was issued on Feb. 4, 1992. The prior art encoding/decoding system codes input digital signals sequentially on the basis of frequencies of occurrence of the input digital signals, and decodes the encoded signals sequentially, to thereby improve encoding efficiency. A sequential list of the encoding system receives and stores encoded data, outputs a list address in which the received encoded data are stored and moves the stored encoded data to a predetermined location every time encoding is performed, so as to update the first sequential list. A variable length encoder performs variable length coding on the basis of how frequently list addresses in the sequential list are used such that a shorter codeword is allocated to a more frequently used list address and a longer codeword is allocated to a less frequently used list address. Thus, an average code length can be shortened and encoding efficiency can be improved.